
import java.util.Iterator;
import java.util.NoSuchElementException;


public class LinkedList implements Iterable{
	private Link head;
	private Link tail;

	
	/**
	 * Instantiates a new linked list.
	 * 
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	public LinkedList() {
		head=null;
		tail=null;
	}
	
	/**
	 * Adds the given data as the head element in the list.
	 *
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 * @param data the data
	 */
	public void addFirst(Object data){
		if (this.isEmpty()) { //new list
			head = new Link(data,null,null);
			tail = new Link(data,null,null);
		}
		else {
			Link temp;
			if (head.getNext()==null) { //so we have only 1 object
				temp= new Link(head.getData(),tail,null);
				head = new Link(data, tail,null);
			}
			else {
				temp= new Link(head.getData(),head.getNext(),null);
				head = new Link(data,temp,null);
				temp.setPrev(head);
				temp.getNext().setPrev(temp);
			}
		}
	}
	
	/**
	 * Removes the head element in the list.
	 *  
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	public void removeFirst(){
		if (!this.isEmpty()){
			if (head.getNext()==null) { //so we have only 1 object
				head = null;
				tail = null;
			}
			else {
				head = head.getNext();
				head.setPrev(null);
			}
		}
		else{
			 throw new NoSuchElementException();
		}
	}
	
	/**
	 * Adds the given data as the tail element in the list.
	 *
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 * @param data the data
	 */
	public void addLast(Object data){
		if (this.isEmpty()) { //new list, same as addFirst
			head = new Link(data,null,null);
			tail = new Link(data,null,null);
		}
		else {
			if (tail.getPrev()==null) { //so we have only 1 object
				tail.setData(data);
				tail.setPrev(head);
				head.setNext(tail);
			}
			else {
				Link temp = new Link(tail.getData(),null,tail.getPrev());
				tail = new Link(data,null,temp);
				temp.setNext(tail);
				temp.getPrev().setNext(temp);
			}
		}
	}
	
	/**
	 * Removes the tail element in the list.
	 * 
	 *  @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	public void removeLast(){
		if (!isEmpty()){
			if (tail.getPrev()==null) { //so we have only 1 object
				tail = null;
				head = null;
			}
			else {
				tail = tail.getPrev();
				tail.setNext(null);
			}
		}
		else{
			 throw new NoSuchElementException();
		}
	}
	
	/**
	 * Removes the head occurrence of data in the list (if exist). this method is using {@link Object#equals(Object)}.
	 *
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 * @param data the data
	 */
	public void remove(Object data){
		Link temp = head;
		while (temp!=null){
			if (temp.getData().equals(data)) {
				if (temp.getNext()==null)
					this.removeLast();
				else if (temp.getPrev()==null)
					this.removeFirst();
				else
					{
					temp.getPrev().setNext(temp.getNext());
					temp.getNext().setPrev(temp.getPrev());
					}
				return;
			}
			temp=temp.getNext();
		} 
	}
	
	/**
	 * Gets the head element data field.
	 *
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 * @return the head element data
	 */
	public Object getFirst(){
		Object ans=null;
		if (head!=null)
			ans = head.getData();
		else
			 throw new NoSuchElementException();
		return ans;
	}
	
	/**
	 * Gets the tail element data field.
	 *
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 * @return the tail element data
	 */
	public Object getLast(){
		if (isEmpty())
			throw new NoSuchElementException();
		else 
		return this.tail;
	}
	
	/**
	 * Checks if the list is empty.
	 *
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 * @return true, if is empty
	 */
	public boolean isEmpty(){
		return this.head==null;
	}
	
	public void printList(){
		Link temp = head;
		while (temp!=null){
			if (temp.getPrev()!=null) System.out.print(temp.getPrev().getData());
			System.out.print("\t\t");
			if (temp.getData()!=null) System.out.print(temp.getData());
			System.out.print("\t\t");
			if (temp.getNext()!=null) System.out.print(temp.getNext().getData());
			System.out.println();
			temp=temp.getNext();
		} 
	}

	/* (non-Javadoc)
	 * @see java.lang.Iterable#iterator()
	 */
	public Iterator iterator() {
		return new ListIterator(head);
	}
	
	public String toString(){
		if (isEmpty())
			return "[]";
		
		Iterator it = iterator();
		StringBuilder sb = new StringBuilder();
		while (it.hasNext()){			
			sb.append(',');
			sb.append(it.next().toString());
		}
		sb.append(']');
		sb.setCharAt(0, '[');
		return sb.toString();
	}
}
